package outoforder.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author shhjiang_001
 * @create 2020-07-03 10:19
 */
public class Solution438 {
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> list = new ArrayList<>();
        char[] pChars = p.toCharArray();
        char[] sChars = s.toCharArray();
        int[] count = new int[128];
        int[] window = new int[128];
        HashSet<Character> set = new HashSet<>();
        for(char ch:pChars){
            count[ch]++;
            set.add(ch);
        }
        int le = 0;
        int ri = 0;
        int valid = 0;
        while (ri < sChars.length){
            char c = sChars[ri];
            ri++;
            if (count[c] != 0){
                window[c]++;
                if (window[c] == count[c]){
                    valid++;
                }
            }
            while (ri-le >= pChars.length){
                if (valid == set.size()) list.add(le);
                char d = sChars[le];
                le++;
                if (count[d] != 0){
                    if (window[d] == count[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return list;
    }
    @Test
    public void test(){
        findAnagrams("cbaebabacd","abc");
    }
}
